package 题目集.dfs.全排列;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

public class 模板 {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] vis;

    public List<List<Integer>> permute(int[] nums) {
        path.clear();
        res.clear();
        vis = new boolean[nums.length];
        dfs(nums, 0);
        return res;
    }

    public void dfs(int[] nums, int depth) {
        if (depth == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (vis[i]) continue;
            path.add(nums[i]);
            vis[i] = true;
            dfs(nums, depth + 1);
            vis[i] = false;
            path.remove(path.size()-1);
        }
    }

    @Test
    public void test() {
        int[] nums = {1, 2, 3};
        List<List<Integer>> res = permute(nums);
        for (List<Integer> re : res) {
            System.out.println(re);
        }
    }
}
